#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define MAXN 100
int parent[MAXN];								//并查集存储结构
int rnk[MAXN];									//存储结点的秩(近似于高度)

// 并查集初始化
void Init(int n)
{
	for (int i=1; i<=n; i++)
	{
		parent[i]=i;
		rnk[i]=0;
	}
}

// 递归算法：并查集中查找x结点的根结点
int Find(int x)
{
	// 路径压缩
	if (x!=parent[x])
		parent[x] = Find(parent[x]);	
	return parent[x];
}

// 并查集中x和y的两个集合的合并
void Union(int x, int y)
{
	
	int rx=Find(x);
	int ry=Find(y);
	
	// x和y属于同一棵树时返回
	if (rx==ry)
		return;
	
	// rx结点作为ry的孩子
	if (rnk[rx]<rnk[ry])
		parent[rx]=ry;
	
	// 秩相同，合并后rx的秩增1
	else
	{
		if (rnk[rx]==rnk[ry])
			rnk[rx]++;
		parent[ry]=rx; // ry结点作为rx的孩子
	}
}

// 求朋友圈个数
int friends(vector<vector<int>>&v,int n)	
{
	// 初始化并查集
	Init(n);
	
	// 合并并查集
	for(int i=0; i<v.size(); i++)
	{
		int a=v[i][0];
		int b=v[i][1];
		Union(a,b);
	}
	
	// 计算集合个数
	int ans=0;
	for(int i=1;i<=n;i++)
		if (parent[i]==i && rnk[i]>0)
			ans++;
	return ans;
}
	
int main()
{
	int n=5;
	vector<vector<int>> v={{1,3},{1,5},{2,4}};
	
	// 朋友圈个数
	int ans = friends(v, n);
	printf("朋友圈个数=%d\n", ans);
	return 0;
}
